package com.geek.netty.test;


import java.util.*;
import java.util.LinkedList;
import java.util.stream.Collectors;

import static java.util.stream.Collectors.*;

/**
 * @program netty-server
 * @description: sort
 * @author: chanzhugang
 * @create: 2021/08/21 10:18
 */
public class Sort {


    public static void main(String[] args) {
        int[] A = new int[]{1, 9, 2, 8, 3, 7, 4, 6, 5, 6, 8, 9, 0};

        Sort sort = new Sort();

        //  sort.insertSort(A);

        //    sort.selectInsert(A);

        //  sort.bubbleSort(A);

//        sort.mergeSort(A);
//
//        for (int a : A) {
//            System.out.println(a);
//        }


        int[] B = new int[]{1, 2, 2, 3, 4, 3, 3};

        final List<Integer> listA = Arrays.stream(B).boxed().collect(toList());

//        List<Integer> quickResult = sort.quickSort(listA);
//        for (Integer data : quickResult) {
//            System.out.println(data);
//
//        }

//        List<Integer> bucketResult = sort.bucketSort(listA);
//        for (Integer data : bucketResult) {
//            System.out.println(data);
//        }


        Map map = sort.distinctMap(listA);
        System.out.println(map);


    }

    public Map distinctMap(List<Integer> A) {

        Map<Integer, Integer> resultMap = new HashMap<>();

        for (Integer data : A) {

            if (resultMap.containsKey(data)) {
                resultMap.remove(data);
            } else {
                resultMap.put(data, 1);
            }


//            resultMap.put(data, resultMap.get(data) == null ? 1 : resultMap.get(data) + 1);

        }
        return resultMap;
    }

    // 插入
    public void insertSort(int[] A) {
        // 扑克牌： 往有序数组 插入一个元素，找到元素正确索引
        for (int i = 0; i < A.length; i++) {

            // 抓到的牌
            int val = A[i];
            // j 是要插入的正确位置
            int j = i;

            for (; j > 0 && A[j - 1] > val; j--) {
                A[j] = A[j - 1];
            }
            A[j] = val;

        }
    }

    // 选择
    public void selectInsert(int[] A) {
        // 从未排序区间选择最小值放在 已排序区间末尾 ： 交换位置

        for (int i = 0; i < A.length; i++) {
            int minPos = i;
            for (int j = i; j < A.length; j++) {
                if (A[j] < A[minPos]) {
                    // 遍历找最小值索引
                    minPos = j;
                }
            }

            int temp = A[i];
            A[i] = A[minPos];
            A[minPos] = temp;
        }


    }

    // 冒泡
    public void bubbleSort(int[] A) {
        // 比较内层循环相邻元素， 交换位置

        for (int i = 0; i < A.length; i++) {
            boolean flag = false;
            for (int j = 0; j < A.length - 1 - i; j++) {
                if (A[j] > A[j + 1]) {
                    int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;

            }

        }

    }


    // 归并排序 : 二分排序完 再 合并 两个有序数组
    public void mergeSort(int[] A) {
        mergeSort(A, 0, A.length);
    }

    private void mergeSort(int[] a, int l, int r) {
        if (r - l <= 1) {
            return;
        }
        int mid = (l + r) / 2;
        mergeSort(a, l, mid);
        mergeSort(a, mid, r);


        merge(a, l, mid, r);
    }

    private void merge(int[] a, int l, int mid, int r) {

        // 1,3,5 || 2,4,6 合并  利用哨兵
        int[] left = Arrays.copyOfRange(a, l, mid + 1);
        int[] right = Arrays.copyOfRange(a, mid, r + 1);

        // 利用哨兵简化代码
        left[left.length - 1] = right[right.length - 1] = Integer.MAX_VALUE;

        int i = 0, j = 0;
        for (int k = l; k < r; k++) {
            if (left[i] < right[j]) {
                a[k] = left[i++];
            } else {
                a[k] = right[j++];
            }
        }

    }

    // 快排： 需要理解第二种解法（递归）
    public List<Integer> quickSort(List<Integer> A) {
        // 随机取一个数， 分成三个有序区间
        return quick(A);

    }

    private List<Integer> quick(List<Integer> A) {
        // 取第一个数
        if (A.size() <= 1) {
            return A;
        }
        int val = A.get(0);
        List<Integer> left = A.stream().filter(a -> a < val).collect(toList());
        List<Integer> mid = A.stream().filter(a -> a == val).collect(toList());
        List<Integer> right = A.stream().filter(a -> a > val).collect(toList());

        left = quick(left);
        right = quick(right);


        left.addAll(mid);
        left.addAll(right);
        return left;

    }

    // 桶排序
    public List<Integer> bucketSort(List<Integer> A) {
        // 相同元素放在同一个桶， %

        int buckets = 10;

        List<java.util.LinkedList> bucketList = new ArrayList<>();
        for (int i = 0; i < buckets; i++) {
            bucketList.add(new LinkedList());
        }
        for (Integer data : A) {
            bucketList.get(data % buckets).add(data);

        }

        List<Integer> result = new ArrayList<>();
        for (LinkedList list : bucketList) {

            result.addAll(list);
        }
        return result;


    }
}